#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define TRACE(x...) 
#define PRINT(x...) TRACE(printf(x))

char fib[5010][2000];
int n;
int l1, l2;
int carry;
int tmp;
char* best;

void add(int i) { //i is the index of the result
	l1 = strlen(fib[i-1]);
	l2 = strlen(fib[i-2]);
	carry=0;

	for (int j=l1-1, k=l2-1; j>=0 && k>=0; j--, k--) {
		tmp=fib[i-1][j]-'0'+fib[i-2][k]-'0'+carry;
		PRINT("%d\n", tmp);
	
		fib[i][max(k,j)]=tmp%10 + '0';
		PRINT("%d %c\n", max(k,j), fib[i][max(k,j)]); 
	
		if (tmp>=10) carry=1;
		else carry=0;
	}

	if (l1!=l2) {
		if (l1>l2) best=fib[i-1];
		else best = fib[i-2];

		for (int j=max(l1,l2)-min(l1,l2)-1; j>=0; j--) {
			tmp=best[j]+carry-'0';
			fib[i][j]=tmp%10 + '0';

			if (tmp>=10) carry=1;
			else carry=0;
		}
	}

	if (carry) {
		for (int j=max(l1,l2); j>=0; j--) {
			fib[i][j+1]=fib[i][j];
		}

		fib[i][0]='1';
		fib[i][max(l1,l2)+1]='\0';
	}
	else {
		fib[i][max(l1,l2)]='\0';
	}
}

int main() {
	fib[0][0]='0'; fib[1][0]='1';
	fib[0][1]='\0'; fib[1][1]='\0';

	for (int i=2; i<5001; i++) {
		add(i);
	}

	TRACE(
		for (int i=0; i<15; i++)
			printf("%s ", fib[i]);
		printf("\n");
	)

	while (scanf("%d", &n)!=EOF) {
		printf("The Fibonacci number for %d is %s\n", n, fib[n]);
	}
}
